/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package my.algorithms.mcorrea;

/**
 *
 * @author mcorrea
 */
public class NumberMissing {
	
	
	public static void main(String args[]){
		missing1();
		//missing2();
		missing3();
		
		repeating1();
		
	}
	

	
	/**
	 * two unsorted array A[n], B[n+1], with the same values
	 * except B has a extr anumber. 
	 * Find the extra number
	 */
	public static void missing1(){
		int A[] = {1, 3, 2, 5, 6, 8};
		int B[] = {1, 3, 2, 20, 5, 6, 8};
		
		int sumA = 0;
		int sumB = 0;
		
		for(int k =0; k<A.length;k++){
			sumA+=A[k];
			sumB+=B[k];
		}
		sumB+=B[B.length-1];
		int missing = sumB - sumA;
		
		System.out.println("Number missing: "+missing);
	
	}
	
	/**
	 * There are supposed to be 4 billion
	 *	numbers in a file, starting from 1 to 4,000,000,000 but 
	 * unfortunately one number is missing, i.e there are only 3,999,999,999 numbers, Find the missing
	  number.
	 */
	public static void missing2(){
	    
		
		Long n = new Long("4000000000"); //Long.MAX_VALUE ; //4000000000;
		int missingXor = 0;
		int missingExpected = 10000000;
		
		for(long i = 0; i<n;i++){
				if(i!=missingExpected)
					missingXor ^=i;
		}
		System.out.println(missingXor);
	
	
	}
	
	/**
	 * I have an array consisting of 2n+1 elements. n elements in it are
		married, i.e they occur twice in the array, however there is one
		element
		which only appears once in the array. I need to find that number in a
		single pass using constant memory. {assume all are positive numbers}
		Eg :- 3 4 1 3 1 7 2 2 4
		Ans:- 7
	 */
	
	public static void missing3(){
		int numbers[] ={3, 4, 1, 3, 1, 7, 2, 2, 4 };
		int missing =0;
		for(int i = 0; i<numbers.length; i++){
			missing ^=numbers[i];
		}
		System.out.println(missing);
	
	}
	
	
	
	/**
	 You are given an array of n+2 elements. All elements of the array are in range 1 to n. 
	 * And all elements occur once except two numbers which occur twice. 
	 * Find the two repeating numbers.
	 */
	public static void repeating1(){
		int numbers[] ={4, 2, 4, 5, 2, 3, 1 }; // n=5 n+2=7
		int count[] = new int[ numbers.length-2  ]; //count the numbers, and first find on 2 print
		
		for(int i = 0; i<numbers.length; i++){
			count[ numbers[i]-1  ]++;
			if(count[ numbers[i]-1  ] > 1){
				System.out.println("Repeat: "+numbers[i]);
			}
		}
	
	}
	
	
	
	
}
